---

Estimating Lower Bounds on the Length of Protein Polymer Chain Segments using Robot Motion Planning

 

Andrew McKnight, Jing He, Nikos Chrisochoides and Andrey Chernikov.

 

Published in VMASC 2013 Capstone Conference, April, 2013

 

Abstract

 

Computational determination of a protein’s 3D atomic structure remains largely an open question in bioinformatics. Electron cryo-microscopy (CryoEM) produces 3D images– ”density maps”–of molecules, but they must be interpreted to derive the underlying atomic structures. We seek to measure the lengths of segments of protein polymer chains associated with specific regions of the density map. We briefly discuss past efforts, and introduce an analog to robot motion planning as a novel approach. We will show this new approach’s superiority through complexity analysis, and present some experimental results in the 2D case, leaving the 3D case to future work.